import java.awt.event.MouseEvent;
import java.sql.Connection;
import java.util.Scanner;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-04-19
 * Time: 16:59
 */
public class Solution {

    /**
     *
     * @param target  是目标数目
     * @param moneyCount moneyCount[i][0] 是面值  moneyCount[i][1] 是对应面值的个数
     * @return 所需的最少的钱币的数目
     */
    public static int solve(int target, int[][] moneyCount){
        int count = 0;
        int kind = moneyCount.length;
        // 从面值大的开始
        for (int i = kind-1; i >= 0; i--) {
            if(target == 0){
                return count;
            }
            // c 要取 需要的数量与实际有的数目的最小值　
            int c = Math.min(target/moneyCount[i][0], moneyCount[i][1]);
            if(c == 0){
                // 说明面值太大了
                continue;
            }
            // 目标减少
            target -= moneyCount[i][0] * c;
            // 使用的钱币数目增加
            count += c;
            // 对应的钱币的数目减少, 这个可以没有, 因为以后不会在用到了
//            moneyCount[i][1] -= c;
        }
        return -1;
    }


    public static void main(String[] args) {
        int[][] moneyCount = { { 1, 3 }, { 2, 1 }, { 5, 4 }, { 10, 3 }, { 20, 0 }
                ,{50, 1}, { 100, 10 } };
        Scanner scanner = new Scanner(System.in);
        int target;
        System.out.println("请输入要支付的钱");
        target = scanner.nextInt();
        int res = solve(target, moneyCount);
        if (res != -1)
            System.out.println(res);
        else
            System.out.println("No");
    }
}
